import java.util.Stack;
class ListNode_exercise {
     public class ListNode{
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    public  ListNode head;
    //. 删除排序链表中的重复元素
        public ListNode deleteDuplicates(ListNode head) {
            if (head == null) {
                return head;
            }
            ListNode cur= head;
            while (cur.next != null) {
                if (cur.val == cur.next.val) {
                    cur.next = cur.next.next;
                } else {
                    cur=cur.next;
                }
            }
            return head;
        }
//给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
//
//你应当 保留 两个分区中每个节点的初始相对位置。
public ListNode partition(ListNode head, int x) {
        //小于x的部分
        ListNode aa=null;
        ListNode as=null;
        //大于x的部分
        ListNode ba=null;
        ListNode bs=null;
        ListNode cur=head;
        while(cur!=null){
            if(cur.val<x){
                if(aa==null){
                    aa=cur;
                    as=cur;
                }else{
                    as.next=cur;
                    as=as.next;
                }
            }else{
                if(ba==null){
                    ba=cur;
                    bs=cur;
                }else{
                    bs.next=cur;
                    bs=bs.next;
                }
            }
            cur=cur.next;
        }
        //没有小于X的部分
        if(aa==null){
            return ba;//返回大于x的部分
        }
        as.next=ba;//小于x的尾巴链接大于x的头
        if(ba!=null){
            bs.next=null;//手动将大于x的尾部置空
        }
        return aa;
    }
//输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
public int[] reversePrint(ListNode head) {
    Stack<Integer> stack=new Stack<>();
    ListNode cur=head;
    while(cur!=null){
        stack.push(cur.val);
        cur=cur.next;
    }
   int i=0;
    int size=stack.size();
    int [] arr=new int[size];
    while(!stack.empty()){
        arr[i++]=stack.pop();
    }
    return arr;
}
//剑指 Offer 18. 删除链表的节点
public ListNode deleteNode(ListNode head, int val) {
        if(head==null){
            return  null;
        }
        //头删
    if(head.val==val){
        head=head.next;
        return head;
    }
    ListNode cur=head;
    while(cur.next!=null){
        if(cur.next.val==val){
            cur.next=cur.next.next;
            break;
        }
        cur=cur.next;
    }
   return head;
}
//剑指 Offer 22. 链表中倒数第k个节点
public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode fast=head;
    ListNode slow=head;
    while(k>0){
        fast=fast.next;
        k--;
    }
    while(fast!=null){
        fast=fast.next;
        slow=slow.next;
    }
    return slow;
}
//剑指 Offer 24. 反转链表
public ListNode reverseList(ListNode head) {
            ListNode newHead=null;
            ListNode cur=head;
            while(cur!=null){
                ListNode curNext=cur.next;
                cur.next=newHead;
                newHead=cur;
                cur=curNext;
            }
            return newHead;

}
}